翻訳と辞書 Words near each other ・ Private Health Insurance Ombudsman ・ Private health services plan ・ Private healthcare ・ Private Helga Geerhart ・ Private Hell ・ Private Hell 36 ・ Private High School Kolhapur ・ Private highway ・ Private highways in the United States ・ Private hospital ・ Private Hospitals Association (Jordan) ・ Private housing estates in Hong Kong ・ Private housing estates in Sha Tin District ・ Private Idaho ・ Private income ・ Private information retrieval ・ Private intelligence agency ・ Private Internet Access ・ Private Investigations ・ Private Investigations (album) ・ Private investigator ・ Private Investigator (Indian TV Series) ・ Private Investigator! ・ Private investment capital subscription ・ Private investment in public equity ・ Private IP ・ Private island ・ Private Islands (TV series) ・ Private Izzy Murphy ・ Private Jet Expeditions Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Private information retrieval ： ウィキペディア英語版 Private information retrieval In cryptography, a private information retrieval (PIR) protocol allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved. PIR is a weaker version of 1-out-of-n oblivious transfer, where it is also required that the user should not get information about other database items. One trivial, but very inefficient way to achieve PIR is for the server to send an entire copy of the database to the user. In fact, this is the only possible protocol (in the classical or the quantum setting) that gives the user information theoretic privacy for their query in a single-server setting. There are two ways to address this problem: one is to make the server computationally bounded and the other is to assume that there are multiple non-cooperating servers, each having a copy of the database. The problem was introduced in 1995 by Chor, Goldreich, Kushilevitz and Sudan〔 in the information-theoretic setting and in 1997 by Kushilevitz and Ostrovsky in the computational setting. Since then, very efficient solutions have been discovered. Single database (computationally private) PIR can be achieved with constant (amortized) communication and k-database (information theoretic) PIR can be done with $n^)\}$ communication. ==Advances in computational PIR== The first single-database computational PIR scheme to achieve communication complexity less than $n$ was created in 1997 by Kushilevitz and Ostrovsky 〔 and achieved communication complexity of $n^\backslash epsilon$ for any $\backslash epsilon$, where $n$ is the number of bits in the database. The security of their scheme was based on the well-studied Quadratic residuosity problem. In 1999, Christian Cachin, Silvio Micali and Markus Stadler achieved poly-logarithmic communication complexity. The security of their system is based on the Phi-hiding assumption. In 2004, Helger Lipmaa achieved log-squared communication complexity $O(\backslash ell\; \backslash log\; n+k\; \backslash log^2\; n)$, where $\backslash ell$ is the length of the strings and $k$ is the security parameter. The security of his system reduces to the semantic security of a length-flexible additively homomorphic cryptosystem like the Damgård–Jurik cryptosystem. In 2005 Craig Gentry and Zulfikar Ramzan achieved log-squared communication complexity which retrieves log-square (consecutive) bits of the database. The security of their scheme is also based on a variant of the Phi-hiding assumption. All previous sublinear-communication computational PIR protocol required linear computational complexity of $\backslash Omega\; (n)$ public-key operations. In 2009, Helger Lipmaa designed a computational PIR protocol with communication complexity $O(\backslash ell\; \backslash log\; n+k\; \backslash log^2\; n)$ and worst-case computation of $O\; (n\; /\; \backslash log\; n)$ public-key operations. Amortization techniques that retrieve non-consecutive bits have been considered by Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai. As shown by Ostrovsky and Skeith, the schemes by Kushilevitz and Ostrovsky 〔 and Lipmaa 〔 use similar ideas based on homomorphic encryption. The Kushilevitz and Ostrovsky protocol is based on the Goldwasser–Micali cryptosystem while the protocol by Lipmaa is based on the Damgård–Jurik cryptosystem. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Private information retrieval」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.